package com.ruoyi.learn.java.algorithm.recursionDivideandConquer;

import java.util.Arrays;

/**
 * 实例 2: 快速排序 (Quick Sort)
 * 快速排序也是分治法，但它的“合并”步骤是隐式的。
 * 问题: 对一个数组进行排序。
 * 分解: 选择一个基准元素 (pivot)，将数组重新排列，使得比基准小的元素都在其左边，比基准大的元素都在其右边。这个过程称为分区 (Partition)。
 * 解决: 递归地对基准左边的子数组和右边的子数组进行快速排序。
 * 合并: 不需要显式的合并步骤，因为分区操作已经将元素放到了正确的位置（相对于基准）。
 */
public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) { // 基本情况：当 low >= high 时，子数组已有序
            // 1. 分解 (分区，得到基准的最终位置)
            int pivotIndex = partition(arr, low, high);

            // 2. 解决
            quickSort(arr, low, pivotIndex - 1); // 排序基准左边
            quickSort(arr, pivotIndex + 1, high); // 排序基准右边
            // 3. 合并 (隐式完成，分区后数组相对有序)
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = low - 1; // i 指向小于基准的区域的最后一个位置

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        // 将基准放到正确位置 (i+1)
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted: " + Arrays.toString(arr));
    }
}